<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>4125：[AMPPZ 2012]Formula One</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[AMPPZ 2012]Formula One</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[AMPPZ 2012]Formula One</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [AMPPZ 2012]Formula One                </h1>
                <p>时间限制：10s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：128MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><div>Little Bytie really enjoys watching Formula One races which are held annually on a track between Bytetown and Byteburg. The most exciting moments for him are overtakes. He would like to see as many of them as possible.</div>
<div>Bytie is dreaming of a race in which N Formula One cars compete and the car that started the race at the i-th position (for each 1&lt;i&lt;N) performs Ai overtakes during the race. We assume for simplicity that at each moment of time at most one overtaking takes place, in which exactly two cars participate (that is, one car goes past another car).</div>
<div>Bytie is wondering whether such a race is possible at all. Could you help him figure this out?</div>
<div>
<div>有 n 辆赛车，从 1 到 n 依次出发。比赛结束时，你听说第 i 辆车超了 ai</div>
<div>次车。你想判断是否存在一种超车方案满足他所说的。</div>
<div>我们定义，在任意时刻最多只发生一次超车，即恰好两辆车参与这次超车</div>
<div>（一辆车超上了另一辆车）。不存在多辆车同时超过一辆车的情况。</div>
</div>
<p></p></p><hr/><h3>输入格式</h3><p><div>The first line of input contains one positive integer i that represents the number of test cases that follow.</div>
<div>Each test case is described in two lines. The first line contains one integer N(1&lt;=N&lt;=1000 000): the number of cars that participate in the race. The second line holds a sequence of N integers A1,A2&hellip;.An(0&lt;=Ai&lt;=10^9) &nbsp;that gives the number of overtakes performed by the respective cars.</div>
<div>The size of a single input file does not exceed 20MB.</div>
<p></p></p><hr/><h3>输出格式</h3><p><div>Your program should output T lines containing answers to the respective test cases. Each line should hold a single word TAK (Polish for yes) or NIE (Polish for no) depending on whether the race described by the test case is possible or not.</div>
<p></p></p><hr/><h3>样例输入</h3><pre>3
2
0 1
3
0 1 4
3
1 1 3
</pre><hr/><h3>样例输出</h3><pre>TAK
NIE
TAK
</pre><hr/><h3>提示</h3><p>没有写明提示</p><hr/><h3>题目来源</h3><p>没有写明来源</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=4125" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=4125" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>